package junior.回溯法;

public class 回溯算法框架_组合 {
    static int[] stack = new int[1000]; // 状态位
    static int[] check = new int[1000]; // 0: 未使用，1：使用
    static int top = 0;
    static int total = 0;
    public static void main(String[] args) {
        fun1(0);
        System.out.println("total: "+total);
    }

    /**
     * n=3个元素里面取 n=3 个，进行排列（元素，可以重复，且有顺序排列）
     * @param n
     */
    public static void fun1(int n){
        if(n == 3){  // n 个元素里面选 r个元素。r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
            show();
            total++;
            return;
        }
        for (int i = 1; i <= 2; i++) {  // n 个元素
            if(top > 0 && stack[top-1] >= i){
                continue;
            }
            if(check[i] == 0 ){ // r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
                check[i] = 1;
                stack[top++] = i;
                fun1(n+1);
                top--;
                check[i] = 0;
            }
        }
    }
    public static void show(){      // 展示每一次的结果
        for (int i = 0; i < top; i++) {
            System.out.print(stack[i]+"\t");
        }
        System.out.println();
    }
}
